package hash;

public class Hash {
    static class Node {
        int key;
        int val;
        Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node[] elem = new Node[10];
    private int useSize;

    private static final double DEFAULT_LOAD_FACTOR = 0.75;

    //插入数据
    public void put(int key,int val) {

        //是否已经存在 key ,存在则更新 val 值
        int index = key % elem.length;
        Node cur = elem[index];
        while(cur != null) {
            if(cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }

        //头插法
        Node node = new Node(key, val);
        node.next = elem[index];
        elem[index] = node;
        useSize++;

        //检测是否超过负载因子
        if(checkCurrentLoad() >= DEFAULT_LOAD_FACTOR) {
            resize();
        }
    }

    private void resize() {
        Node[] newArray = new Node[elem.length * 2];

        for (int i = 0; i < elem.length; i++) {
            Node cur = elem[i];
            while(cur != null) {
                Node curN = cur.next;

                int index = cur.key % newArray.length;
                cur.next = newArray[index];
                newArray[index] = cur;

                cur = curN;
            }
        }

        elem = newArray;
    }

    //检测当前的负载量
    private double checkCurrentLoad() {
        return useSize * 1.0 / elem.length;
    }

    //获取 val 值
    public int get(int key) {
        int index = key % elem.length;
        Node cur = elem[index];
        while(cur != null) {
            if(cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

    public static void main(String[] args) {
        Hash hashBuck = new Hash();
        hashBuck.put(1,111);
        hashBuck.put(11,111111);
        hashBuck.put(14,141414);
        hashBuck.put(4,444);
        hashBuck.put(2,222);
        hashBuck.put(15,151515);
        hashBuck.put(6,666);
        hashBuck.put(5,555);

        System.out.println(hashBuck.get(15));

    }
}
